package pers.qianyu.month_202012.date_20201212;

import java.util.*;

/**
 * 1019. 链表中的下一个更大节点
 * https://leetcode-cn.com/problems/next-greater-node-in-linked-list/
 *
 * @author mizzle rain
 * @date 2020-12-12 17:15
 */
public class NextLargerNodes {
    public int[] nextLargerNodes(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            list.add(cur.val);
        }
        int size = list.size();
        int[] res = new int[size];
        Stack<Integer> s = new Stack<>();
        for (int i = size - 1; i >= 0; i--) {
            int val = list.get(i);
            while (!s.isEmpty() && s.peek() <= val) {
                s.pop();
            }
            res[i] = s.isEmpty() ? 0 : s.peek();
            s.push(val);
        }
        return res;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
